package com.hanxiaozhang.recursion.violentrecursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈打印一个字符串的全部子序列
 *   打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
 *   〉
 *
 * @author hanxinghua
 * @create 2021/10/12
 * @since 1.0.0
 */
public class PrintAllSubsquences {


    public static void main(String[] args) {
        String test = "aacc";
        List<String> result1 = subs(test);
        List<String> result2 = subsNoRepeat(test);

        for (String str : result1) {
            System.out.println(str);
        }
        System.out.println("=================");
        for (String str : result2) {
            System.out.println(str);
        }
        System.out.println("=================");

    }


    /**
     * 打印一个字符串的全部子序列
     *
     * @param s
     * @return
     */
    public static List<String> subs(String s) {
        // 把字符串拆成字节数组
        char[] str = s.toCharArray();
        String subStr = "";
        // 子串结果集合
        List<String> result = new ArrayList<>();
        process1(str, 0, result, subStr);
        return result;
    }

    /**
     * 递归
     *
     * @param str 字符数组
     * @param index 处理的位置
     * @param result 子串结果集合
     * @param subStr  子串
     */
    public static void process1(char[] str, int index, List<String> result, String subStr) {
        // 如果处理位置等于数组长度，停止递归，将结构添加进入集合
        if (index == str.length) {
            result.add(subStr);
            return;
        }
        // 两种情况:不使用当前位置字符，使用当前位置字符
        String no = subStr;
        process1(str, index + 1, result, no);
        String yes = subStr + String.valueOf(str[index]);
        process1(str, index + 1, result, yes);
    }


    /**
     * 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
     * 区别，使用set存储结果
     *
     *
     * @param s
     * @return
     */
    public static List<String> subsNoRepeat(String s) {
        char[] str = s.toCharArray();
        String subStr = "";
        HashSet<String> set = new HashSet<>();
        process2(str, 0, set, subStr);
        List<String> result = new ArrayList<>();
        for (String cur : set) {
            result.add(cur);
        }
        return result;
    }

    public static void process2(char[] str, int index, HashSet<String> set, String subStr) {
        if (index == str.length) {
            set.add(subStr);
            return;
        }
        String no = subStr;
        process2(str, index + 1, set, no);
        String yes = subStr + String.valueOf(str[index]);
        process2(str, index + 1, set, yes);
    }

}
